package com.arithmeticEveryDay.leetCode;

import java.util.Scanner;
/*

检查是否可行的方法：
放在(i, j)的位置上，那么要检查(c, j), (i+c, j+c), (i-c, j+c)，其中c是满足坐标在棋盘上的任意整数
以八皇后问题为例，
如果我要放在(4, 2)的位置上，
那么要检查前面放置的皇后的位置在不在(4, 2)的攻击范围内



            00                          01              02              03
  /  /  /  / | \ \  \
10 11 12 13 14 15 16 17
...



 */
public class Solution52 {
    
    public int totalNQueens(int n) {
        int[] board = new int[n];
        int count = dfs(n, board, 0, 0);
        return count;
    }

    private int dfs(int n, int[] board, int row, int count) {
        // System.out.println(Arrays.toString(board));
        if (row == n) {
            count++;
            // System.out.println(Arrays.toString(board));
        }
        for (int k = 0; k < n; k++) {
            if (doable(n, board, row, k)) {
                board[row] = k;
                count = dfs(n, board, row+1, count);
            }
        }
        return count;
    }

    private boolean doable(int n, int[] board, int row, int col) {
        for (int k = 0; k < row; k++) {
            if (board[k] == col || Math.abs(k - row) == Math.abs(board[k] - col)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        Solution52 s = new Solution52();
        System.out.println(s.totalNQueens(n));

    }

}
